package Fundamental.sort;

import java.util.Arrays;
import java.util.Objects;

public class ShellSort {
    public static void main(String[] args) {
        int[] a = { -1 , -2 ,  8 ,2 ,1 , 18 , 21 , 20 , 3 , 4};
//        sort(a);
        System.out.println(Arrays.toString(a));
        Node node = new Node();
        Node current = node;
        Node pre = null ;
        for (int i = 0 ; i < a.length ; i++) {
            current.setIndex(i);
            if(!Objects.isNull(pre)) {
                pre.setNextIndex(current);
            }
            current.setPreIndex(pre);
            pre = current;
            current = new Node();
        }
//        swapNode(node , pre , a);
        moveNode(node , pre , a);
        forNode(node, a);
        System.out.println("\n"+Arrays.toString(a));
    }
    public static void swap(int[] array , int from , int to){
        int temp = array[from];
        array[from] = array[to];
        array[to] = temp ;
    }
    public static void swapNode(Node N1 , Node N2 , int[] array){
        // 获得 pre 的前后指针
       if(Objects.isNull(N1) || Objects.isNull(N2)){
           return;
       }
       Node pre1 = N1.getPreIndex();
       Node next1 = N1.getNextIndex();
       // 获得 next 的前后指针
       Node pre2 = N2.getPreIndex();
       Node next2 = N2.getNextIndex();

       // 提前 N1 的位置
       if(!Objects.isNull(pre1)){
           if(pre1.equals(N2)){
               if(!Objects.isNull(pre1.getPreIndex())){
                   pre1.getPreIndex().setNextIndex(N1);
               }
           }else{
               pre1.setNextIndex(N2);
           }
       }
       if(N2.equals(pre1)){
          N2.setPreIndex(N1);
       }else{
          N2.setPreIndex(pre1);
       }

       if(N2.equals(next1)){
           N2.setNextIndex(N1);
       }else {
           N2.setNextIndex(next1);
       }
       if(!Objects.isNull(next1)){
           if(next1.equals(N2)){
             if(!Objects.isNull(next1.getNextIndex())){
                 next1.getNextIndex().setPreIndex(N1);
             }
           }else{
             next1.setPreIndex(N2);
           }
       }

       // 后退 N2 的位置
       if(!Objects.isNull(pre2)) {
           if(pre2.equals(N1)){
               if(!Objects.isNull(pre2.getPreIndex())){
                   pre2.getNextIndex().setNextIndex(N1);
               }
           }else{
               pre2.setNextIndex(N1);
           }
       }
       if(N1.equals(pre2)){
           N1.setPreIndex(N2);
       }else{
           N1.setPreIndex(pre2);
       }
       if(N1.equals(next2)){
          N1.setNextIndex(N2);
       }else{
          N1.setNextIndex(next2);
       }
       if(!Objects.isNull(next2)){
           if(next2.equals(N1)){
              if(!Objects.isNull(next2.getNextIndex())){
                next2.getNextIndex().setPreIndex(N2);
              }
           }else{
               next2.setPreIndex(N1);
           }
       }

       // 先将 array 中交换位置
       swap(array,N1.getIndex(),N2.getIndex());
       // 交换 index 中的数值
       int temp = N1.getIndex() ;
       N1.setIndex(N2.getIndex());
       N2.setIndex(temp);
    }
    public static void forNode(Node head , int[] array){
        Node current = head ;
        while(!Objects.isNull(current)){
            // do
            System.out.print(array[current.getIndex()] + " , ");
            // 指针后移
            current = current.getNextIndex();
        }
    }
    public static void sort(int[] array ){
        int interval = 4 ;
        Node subArray = null ;
        Node pre = null ;
        while (interval >= 1){
            subArray = findSubArray(array , interval);
            System.out.println("interval: " + interval );
            subArray = subArray.getNextIndex();
            while(!Objects.isNull(subArray)){
                pre = subArray.getPreIndex();

                while(!Objects.isNull(pre)){
                    System.out.print(pre.getIndex() + " , ");
                    pre = pre.getPreIndex();
                }
                System.out.println();
                subArray = subArray.getNextIndex();
            }
            interval = interval >> 1;
        }

    }
    /**
     * 利用双向链表实现的插入排序
     * */
    private static void insertSort(Node head , int[] array){
        Node current = head ;
        Node pre = null ;
        Node swapNode = null ;
        int temp = 0 ;
        Node biggerOne = null;

        // 遍历到最后一个元素
        while(!Objects.isNull(current)){
            // 从头开始找到第一个比 temp 大的数
            biggerOne = findFirstBiggerOne(head , array[current.getIndex()] , array);

            current = current.getNextIndex();
        }
        //
    }
    /**
     *平移数组
     * */
    private static void moveNode(Node stopPoint , Node startNode , int[] array){
        Node current = startNode ;
        Node swapNode = null ;
        while(!Objects.isNull(current) && !stopPoint.equals(current)){
            swapNode = current;
            swapNode(swapNode , swapNode.getPreIndex() , array);
        }
        swapNode(stopPoint , stopPoint.getNextIndex() , array);
    }

    private static Node findFirstBiggerOne(Node head , int target , int[] array){
        Node current = head;
        while(!Objects.isNull(current)){
            if(array[current.getIndex()] >= target){
                return current ;
            }
            current = current.getNextIndex();
        }
        return null ;
    }
    /**
     *查找 interval 对应的子集合
     * */
    private static Node findSubArray(int[] array, int interval) {
        int nextElementIndex = 0 ;
        Node head = new Node();
        head.setIndex(-1);
        Node pre = head ;
        Node current = null ;
        while(nextElementIndex < array.length){
            current = new Node();
            current.setIndex(nextElementIndex);
            nextElementIndex += interval;
            pre.setNextIndex(current);
            current.setPreIndex(pre);
            pre = current ;
        }
        return head ;
    }
    public static class Node{

        private int index ;
        private Node nextIndex ;
        private Node preIndex ;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return index == node.index ;
        }

        @Override
        public int hashCode() {
            return Objects.hash(index, nextIndex, preIndex);
        }

        public Node getPreIndex() {
            return preIndex;
        }

        public void setPreIndex(Node preIndex) {
            this.preIndex = preIndex;
        }

        public Node getNextIndex() {
            return nextIndex;
        }

        public void setNextIndex(Node nextIndex) {
            this.nextIndex = nextIndex;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "index=" + index +
                    '}';
        }
    }
}
